package com.mashibing.class22;

/**
 * 给定3个参数，N，M，K
 * 怪兽有N滴血，等着英雄来砍自己
 * 英雄每一次打击，都会让怪兽流失[0~M]的血量
 * 到底流失多少？每一次在[0~M]上等概率的获得一个值
 * 求K次打击之后，英雄把怪兽砍死的概率
 */
public class Code01_KillMonster {
    /**
     * @param N 怪兽一共有N滴血
     * @param M 每砍随机掉 1 - M滴血
     * @param K 一共砍K次.
     * @return
     */
    public static double right(int N, int M, int K) {
        if (N < 1 || M < 1 || K < 1) {
            return 0;
        }
        long all = (long) Math.pow(M + 1, K);
        long kill = process(K, M, N);
        return (double) ((double) kill / (double) all);
    }

    // 怪兽还剩hp点血
    // 每次的伤害在[0~M]范围上
    // 还有times次可以砍
    // 返回砍死的情况数！
    // times 做行; hp 做列
    public static long process(int times, int M, int hp) {
        if (times == 0) { // 还剩下0次可以砍的时候.
            // hp<=0 代表怪兽已经被砍死.
            return hp <= 0 ? 1 : 0;
        }
        if (hp <= 0) {
            return (long) Math.pow(M + 1, times);
        }
        long ways = 0;
        // 让怪兽掉 0滴血,1滴血....一直到M滴血.
        for (int i = 0; i <= M; i++) {
            ways += process(times - 1, M, hp - i);
        }
        return ways;
    }

    public static double dp1(int N, int M, int K) {
        if (N < 1 || M < 1 || K < 1) {
            return 0;
        }
        long all = (long) Math.pow(M + 1, K);
        // 行对应的是还有多少刀可以砍
        // 列对应的是还剩下多少滴血.
        long[][] dp = new long[K + 1][N + 1];
        dp[0][0] = 1;
        for (int times = 1; times <= K; times++) {
            dp[times][0] = (long) Math.pow(M + 1, times);
            for (int hp = 1; hp <= N; hp++) {
                long ways = 0;
                for (int i = 0; i <= M; i++) {
                    if (hp - i >= 0) {
                        ways += dp[times - 1][hp - i];
                    } else {
                        // 获得 (long) Math.pow(M + 1, times - 1) 这么多生存点.
                        ways += (long) Math.pow(M + 1, times - 1);
                    }
                }
                //dp[times][hp] 的值依赖于 dp[times][hp-0]+dp[times][hp-1]+...+dp[times][hp-M]
                dp[times][hp] = ways;
            }
        }
        long kill = dp[K][N];
        return (double) ((double) kill / (double) all);
    }

    public static double dp2(int N, int M, int K) {
        if (N < 1 || M < 1 || K < 1) {
            return 0;
        }
        long all = (long) Math.pow(M + 1, K);
        long[][] dp = new long[K + 1][N + 1];
        dp[0][0] = 1;
        for (int times = 1; times <= K; times++) {
            dp[times][0] = (long) Math.pow(M + 1, times);
            for (int hp = 1; hp <= N; hp++) {
                // dp[times][hp] 它的值依赖于
                // dp[time-1][hp-0],dp[time-1][hp-1],dp[time-1][hp-2],....dp[time-1][hp-M] 之和
                // dp[times][hp-1] 它的值依赖于 dp[time-1][hp-1],dp[time-1][hp-2],....dp[time-1][hp-1-M] 之和
                // 所以 dp[times][hp] = dp[times][hp-1] + dp[times - 1][hp]
                // =  dp[time-1][hp-M]+dp[time-1][hp-1]+dp[time-1][hp-2]+.... +dp[time-1][hp-1-M]
                // 但是多加了一个 dp[time-1][hp-1-M] 需要把它减掉.
                dp[times][hp] = dp[times][hp - 1] + dp[times - 1][hp];
                // 下面的代码 就是把 dp[time-1][hp-1-M]减掉.
                if (hp - 1 - M >= 0) {
                    dp[times][hp] -= dp[times - 1][hp - 1 - M];
                } else {
                    dp[times][hp] -= Math.pow(M + 1, times - 1);
                }
            }
        }
        long kill = dp[K][N];
        return (double) ((double) kill / (double) all);
    }

    public static void main(String[] args) {
        int NMax = 10;
        int MMax = 10;
        int KMax = 10;
        int testTime = 200;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int N = (int) (Math.random() * NMax);
            int M = (int) (Math.random() * MMax);
            int K = (int) (Math.random() * KMax);
            double ans1 = right(N, M, K);
            double ans2 = dp1(N, M, K);
            double ans3 = dp2(N, M, K);
            if (ans1 != ans2 || ans1 != ans3) {
                System.out.println("Oops!");
                break;
            }
        }
        System.out.println("测试结束");
    }
}
